// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/backend/instruction-scheduler.h"

#include "src/base/adapters.h"
#include "src/base/utils/random-number-generator.h"
#include "src/isolate.h"

#include "src/objects-inl.h" // weolar

namespace v8 {
namespace internal {
    namespace compiler {

        void InstructionScheduler::SchedulingQueueBase::AddNode(
            ScheduleGraphNode* node)
        {
            // We keep the ready list sorted by total latency so that we can quickly find
            // the next best candidate to schedule.
            auto it = nodes_.begin();
            while ((it != nodes_.end()) && ((*it)->total_latency() >= node->total_latency())) {
                ++it;
            }
            nodes_.insert(it, node);
        }

        InstructionScheduler::ScheduleGraphNode*
        InstructionScheduler::CriticalPathFirstQueue::PopBestCandidate(int cycle)
        {
            DCHECK(!IsEmpty());
            auto candidate = nodes_.end();
            for (auto iterator = nodes_.begin(); iterator != nodes_.end(); ++iterator) {
                // We only consider instructions that have all their operands ready.
                if (cycle >= (*iterator)->start_cycle()) {
                    candidate = iterator;
                    break;
                }
            }

            if (candidate != nodes_.end()) {
                ScheduleGraphNode* result = *candidate;
                nodes_.erase(candidate);
                return result;
            }

            return nullptr;
        }

        InstructionScheduler::ScheduleGraphNode*
        InstructionScheduler::StressSchedulerQueue::PopBestCandidate(int cycle)
        {
            DCHECK(!IsEmpty());
            // Choose a random element from the ready list.
            auto candidate = nodes_.begin();
            std::advance(candidate, isolate()->random_number_generator()->NextInt(static_cast<int>(nodes_.size())));
            ScheduleGraphNode* result = *candidate;
            nodes_.erase(candidate);
            return result;
        }

        InstructionScheduler::ScheduleGraphNode::ScheduleGraphNode(Zone* zone,
            Instruction* instr)
            : instr_(instr)
            , successors_(zone)
            , unscheduled_predecessors_count_(0)
            , latency_(GetInstructionLatency(instr))
            , total_latency_(-1)
            , start_cycle_(-1)
        {
        }

        void InstructionScheduler::ScheduleGraphNode::AddSuccessor(
            ScheduleGraphNode* node)
        {
            successors_.push_back(node);
            node->unscheduled_predecessors_count_++;
        }

        InstructionScheduler::InstructionScheduler(Zone* zone,
            InstructionSequence* sequence)
            : zone_(zone)
            , sequence_(sequence)
            , graph_(zone)
            , last_side_effect_instr_(nullptr)
            , pending_loads_(zone)
            , last_live_in_reg_marker_(nullptr)
            , last_deopt_or_trap_(nullptr)
            , operands_map_(zone)
        {
        }

        void InstructionScheduler::StartBlock(RpoNumber rpo)
        {
            DCHECK(graph_.empty());
            DCHECK_NULL(last_side_effect_instr_);
            DCHECK(pending_loads_.empty());
            DCHECK_NULL(last_live_in_reg_marker_);
            DCHECK_NULL(last_deopt_or_trap_);
            DCHECK(operands_map_.empty());
            sequence()->StartBlock(rpo);
        }

        void InstructionScheduler::EndBlock(RpoNumber rpo)
        {
            if (FLAG_turbo_stress_instruction_scheduling) {
                ScheduleBlock<StressSchedulerQueue>();
            } else {
                ScheduleBlock<CriticalPathFirstQueue>();
            }
            sequence()->EndBlock(rpo);
            graph_.clear();
            last_side_effect_instr_ = nullptr;
            pending_loads_.clear();
            last_live_in_reg_marker_ = nullptr;
            last_deopt_or_trap_ = nullptr;
            operands_map_.clear();
        }

        void InstructionScheduler::AddTerminator(Instruction* instr)
        {
            ScheduleGraphNode* new_node = new (zone()) ScheduleGraphNode(zone(), instr);
            // Make sure that basic block terminators are not moved by adding them
            // as successor of every instruction.
            for (ScheduleGraphNode* node : graph_) {
                node->AddSuccessor(new_node);
            }
            graph_.push_back(new_node);
        }

        void InstructionScheduler::AddInstruction(Instruction* instr)
        {
            ScheduleGraphNode* new_node = new (zone()) ScheduleGraphNode(zone(), instr);

            // We should not have branches in the middle of a block.
            DCHECK_NE(instr->flags_mode(), kFlags_branch);
            DCHECK_NE(instr->flags_mode(), kFlags_branch_and_poison);

            if (IsFixedRegisterParameter(instr)) {
                if (last_live_in_reg_marker_ != nullptr) {
                    last_live_in_reg_marker_->AddSuccessor(new_node);
                }
                last_live_in_reg_marker_ = new_node;
            } else {
                if (last_live_in_reg_marker_ != nullptr) {
                    last_live_in_reg_marker_->AddSuccessor(new_node);
                }

                // Make sure that instructions are not scheduled before the last
                // deoptimization or trap point when they depend on it.
                if ((last_deopt_or_trap_ != nullptr) && DependsOnDeoptOrTrap(instr)) {
                    last_deopt_or_trap_->AddSuccessor(new_node);
                }

                // Instructions with side effects and memory operations can't be
                // reordered with respect to each other.
                if (HasSideEffect(instr)) {
                    if (last_side_effect_instr_ != nullptr) {
                        last_side_effect_instr_->AddSuccessor(new_node);
                    }
                    for (ScheduleGraphNode* load : pending_loads_) {
                        load->AddSuccessor(new_node);
                    }
                    pending_loads_.clear();
                    last_side_effect_instr_ = new_node;
                } else if (IsLoadOperation(instr)) {
                    // Load operations can't be reordered with side effects instructions but
                    // independent loads can be reordered with respect to each other.
                    if (last_side_effect_instr_ != nullptr) {
                        last_side_effect_instr_->AddSuccessor(new_node);
                    }
                    pending_loads_.push_back(new_node);
                } else if (instr->IsDeoptimizeCall() || instr->IsTrap()) {
                    // Ensure that deopts or traps are not reordered with respect to
                    // side-effect instructions.
                    if (last_side_effect_instr_ != nullptr) {
                        last_side_effect_instr_->AddSuccessor(new_node);
                    }
                    last_deopt_or_trap_ = new_node;
                }

                // Look for operand dependencies.
                for (size_t i = 0; i < instr->InputCount(); ++i) {
                    const InstructionOperand* input = instr->InputAt(i);
                    if (input->IsUnallocated()) {
                        int32_t vreg = UnallocatedOperand::cast(input)->virtual_register();
                        auto it = operands_map_.find(vreg);
                        if (it != operands_map_.end()) {
                            it->second->AddSuccessor(new_node);
                        }
                    }
                }

                // Record the virtual registers defined by this instruction.
                for (size_t i = 0; i < instr->OutputCount(); ++i) {
                    const InstructionOperand* output = instr->OutputAt(i);
                    if (output->IsUnallocated()) {
                        operands_map_[UnallocatedOperand::cast(output)->virtual_register()] = new_node;
                    } else if (output->IsConstant()) {
                        operands_map_[ConstantOperand::cast(output)->virtual_register()] = new_node;
                    }
                }
            }

            graph_.push_back(new_node);
        }

        template <typename QueueType>
        void InstructionScheduler::ScheduleBlock()
        {
            QueueType ready_list(this);

            // Compute total latencies so that we can schedule the critical path first.
            ComputeTotalLatencies();

            // Add nodes which don't have dependencies to the ready list.
            for (ScheduleGraphNode* node : graph_) {
                if (!node->HasUnscheduledPredecessor()) {
                    ready_list.AddNode(node);
                }
            }

            // Go through the ready list and schedule the instructions.
            int cycle = 0;
            while (!ready_list.IsEmpty()) {
                ScheduleGraphNode* candidate = ready_list.PopBestCandidate(cycle);

                if (candidate != nullptr) {
                    sequence()->AddInstruction(candidate->instruction());

                    for (ScheduleGraphNode* successor : candidate->successors()) {
                        successor->DropUnscheduledPredecessor();
                        successor->set_start_cycle(
                            std::max(successor->start_cycle(), cycle + candidate->latency()));

                        if (!successor->HasUnscheduledPredecessor()) {
                            ready_list.AddNode(successor);
                        }
                    }
                }

                cycle++;
            }
        }

        int InstructionScheduler::GetInstructionFlags(const Instruction* instr) const
        {
            switch (instr->arch_opcode()) {
            case kArchNop:
            case kArchFramePointer:
            case kArchParentFramePointer:
            case kArchStackSlot: // Despite its name this opcode will produce a
                // reference to a frame slot, so it is not affected
                // by the arm64 dual stack issues mentioned below.
            case kArchComment:
            case kArchDeoptimize:
            case kArchJmp:
            case kArchBinarySearchSwitch:
            case kArchLookupSwitch:
            case kArchRet:
            case kArchTableSwitch:
            case kArchThrowTerminator:
                return kNoOpcodeFlags;

            case kArchTruncateDoubleToI:
            case kIeee754Float64Acos:
            case kIeee754Float64Acosh:
            case kIeee754Float64Asin:
            case kIeee754Float64Asinh:
            case kIeee754Float64Atan:
            case kIeee754Float64Atanh:
            case kIeee754Float64Atan2:
            case kIeee754Float64Cbrt:
            case kIeee754Float64Cos:
            case kIeee754Float64Cosh:
            case kIeee754Float64Exp:
            case kIeee754Float64Expm1:
            case kIeee754Float64Log:
            case kIeee754Float64Log1p:
            case kIeee754Float64Log10:
            case kIeee754Float64Log2:
            case kIeee754Float64Pow:
            case kIeee754Float64Sin:
            case kIeee754Float64Sinh:
            case kIeee754Float64Tan:
            case kIeee754Float64Tanh:
                return kNoOpcodeFlags;

            case kArchStackPointer:
                // ArchStackPointer instruction loads the current stack pointer value and
                // must not be reordered with instruction with side effects.
                return kIsLoadOperation;

            case kArchWordPoisonOnSpeculation:
                // While poisoning operations have no side effect, they must not be
                // reordered relative to branches.
                return kHasSideEffect;

            case kArchPrepareCallCFunction:
            case kArchSaveCallerRegisters:
            case kArchRestoreCallerRegisters:
            case kArchPrepareTailCall:
            case kArchCallCFunction:
            case kArchCallCodeObject:
            case kArchCallJSFunction:
            case kArchCallWasmFunction:
            case kArchCallBuiltinPointer:
            case kArchTailCallCodeObjectFromJSFunction:
            case kArchTailCallCodeObject:
            case kArchTailCallAddress:
            case kArchTailCallWasm:
            case kArchDebugAbort:
            case kArchDebugBreak:
                return kHasSideEffect;

            case kArchStoreWithWriteBarrier:
                return kHasSideEffect;

            case kWord32AtomicLoadInt8:
            case kWord32AtomicLoadUint8:
            case kWord32AtomicLoadInt16:
            case kWord32AtomicLoadUint16:
            case kWord32AtomicLoadWord32:
                return kIsLoadOperation;

            case kWord32AtomicStoreWord8:
            case kWord32AtomicStoreWord16:
            case kWord32AtomicStoreWord32:
                return kHasSideEffect;

            case kWord32AtomicExchangeInt8:
            case kWord32AtomicExchangeUint8:
            case kWord32AtomicExchangeInt16:
            case kWord32AtomicExchangeUint16:
            case kWord32AtomicExchangeWord32:
            case kWord32AtomicCompareExchangeInt8:
            case kWord32AtomicCompareExchangeUint8:
            case kWord32AtomicCompareExchangeInt16:
            case kWord32AtomicCompareExchangeUint16:
            case kWord32AtomicCompareExchangeWord32:
            case kWord32AtomicAddInt8:
            case kWord32AtomicAddUint8:
            case kWord32AtomicAddInt16:
            case kWord32AtomicAddUint16:
            case kWord32AtomicAddWord32:
            case kWord32AtomicSubInt8:
            case kWord32AtomicSubUint8:
            case kWord32AtomicSubInt16:
            case kWord32AtomicSubUint16:
            case kWord32AtomicSubWord32:
            case kWord32AtomicAndInt8:
            case kWord32AtomicAndUint8:
            case kWord32AtomicAndInt16:
            case kWord32AtomicAndUint16:
            case kWord32AtomicAndWord32:
            case kWord32AtomicOrInt8:
            case kWord32AtomicOrUint8:
            case kWord32AtomicOrInt16:
            case kWord32AtomicOrUint16:
            case kWord32AtomicOrWord32:
            case kWord32AtomicXorInt8:
            case kWord32AtomicXorUint8:
            case kWord32AtomicXorInt16:
            case kWord32AtomicXorUint16:
            case kWord32AtomicXorWord32:
                return kHasSideEffect;

#define CASE(Name) case k##Name:
                TARGET_ARCH_OPCODE_LIST(CASE)
#undef CASE
                return GetTargetInstructionFlags(instr);
            }

            UNREACHABLE();
        }

        void InstructionScheduler::ComputeTotalLatencies()
        {
            for (ScheduleGraphNode* node : base::Reversed(graph_)) {
                int max_latency = 0;

                for (ScheduleGraphNode* successor : node->successors()) {
                    DCHECK_NE(-1, successor->total_latency());
                    if (successor->total_latency() > max_latency) {
                        max_latency = successor->total_latency();
                    }
                }

                node->set_total_latency(max_latency + node->latency());
            }
        }

    } // namespace compiler
} // namespace internal
} // namespace v8
